描述

传送门：Photo of The Sky

Pavel made a photo of his favourite stars in the sky. His camera takes a photo of all points of the sky that belong to some rectangle with sides parallel to the coordinate axes.

Strictly speaking, it makes a photo of all points with coordinates (x,y), such that x1≤x≤x2 and y1≤y≤y2, where (x1,y1) and (x2,y2) are coordinates of the left bottom and the right top corners of the rectangle being photographed. The area of this rectangle can be zero.

After taking the photo, Pavel wrote down coordinates of n of his favourite stars which appeared in the photo. These points are not necessarily distinct, there can be multiple stars in the same point of the sky.

Pavel has lost his camera recently and wants to buy a similar one. Specifically, he wants to know the dimensions of the photo he took earlier. Unfortunately, the photo is also lost. His notes are also of not much help; numbers are written in random order all over his notepad, so it’s impossible to tell which numbers specify coordinates of which points.

Pavel asked you to help him to determine what are the possible dimensions of the photo according to his notes. As there are multiple possible answers, find the dimensions with the minimal possible area of the rectangle.

输入描述

The first line of the input contains an only integer n (1≤n≤100000), the number of points in Pavel’s records.

The second line contains 2⋅n integers a1, a2, …, a2⋅n (1≤ai≤109), coordinates, written by Pavel in some order.

输出描述

Print the only integer, the minimal area of the rectangle which could have contained all points from Pavel’s records.

示例

输入

4
4 1 3 2 3 2 1 3
3
5 8 5 5 7 5

输出

1
2

1
0

题解

题目大意

给你2n个数，任意组合得到n个坐标点，求最小矩形面积能够框住这n个点。

思路

我们先将这2n个数排序得到a1,a2…a2n，然后考虑一下问题的转化：我们应该如何计算矩形的面积？

因为矩形是要求把这n个点框住的，所以稍微想一下不难得到：S=(max(x)−min(x))∗(max(y)−min(y))
于是我们将原问题这样转化：
给你2n个数，把这2n个数放在两个集合当中，每个集合的元素个数为n，设这两个集合分别为X,Y， 
求min((Xmax−Xmin)∗(Ymax−Ymin))
接下来我们来讨论，如何分放集合。

考虑如果最大数a2n与最小数a1如果在同一个集合X，那么现在我们要求min(Ymax−Ymin)。

考虑一下怎样的情况才会有min(Ymax−Ymin)的情况出现。假设Ymin在a中为ai，那么Ymax在a中一定为ai+n−1，为什么呢？

如果Ymax在ai+1−>ai+n−2之间，那么Y集合里面的元素个数就没有要求的n个了，不满足。

如果Ymax在ai+n−>a2n−1之间，那么显然可以在满足元素个数为n的情况下使Ymax最小。

所以在最大数a2n与最小数a1如果在同一个集合X时，答案的值为：
Ans=min(a[2n]−a[1])∗(a[i+n−1]−a[i])2≤i≤n
那么还有一种情况就是最大数a2n与最小数a1不在同一个集合当中，与上面类似的讨论不难得到最后的结果唯一：
Ans=(a[2n]−a[n+1])∗(a[n]−a[1])
所以我们最后的结果在上面两者之间取最小即可。

简单方法就排序后,选其中连续的n个数作为x,剩下的按序作为y, 然后用xmax-xmin乘ymax-ymin 取最小解即可

代码

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <stack>
#include <cmath>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int MAXN = 2*1e5 +5;
using namespace std;
int n;
ll a[MAXN];

int main(){
    cin >> n;
    for(int i = 0; i < n+n; i++){
        cin >> a[i];
    }
    sort(a, a+n+n);
    if(n <= 1){
        cout << "0" << endl;
    }
    else{
        ll ans = a[n-1]-a[0];
        ans *= a[n+n-1]-a[n];
        ll l = a[n+n-1]-a[0];
        for(int i = 1; i <= n; i++){
            ans = min(ans, l*(a[i+n-1]-a[i]));
        }
        cout << ans << endl;
    }
}